package com.wkh.datastructure.Heap;

import java.util.Arrays;

//小顶堆实现
public class MinHeap {
    Integer[] array;
    int size;

    public MinHeap(int capacity) {
        this.array = new Integer[capacity];
    }
    //把普通数组转换为大顶堆
    public MinHeap(Integer[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    //建堆操作
    private void heapify(){
        //找到最后一个非叶子节点 i = size/2-1
        for (int i = size/2-1; i >= 0; i--) {
            //下潜操作
            down(i);
        }
    }

    /**
     * 获取堆顶元素
     * @return 返回堆顶元素
     */
    public Integer peek(){
        if(size == 0){
            return null;
        }
        return array[0];
    }

    /**
     * 删除堆顶元素并返回
     * @return 返回堆顶元素
     */
    public Integer poll(){
        //0.获取堆顶元素
        Integer top = array[0];
        //1.把堆顶元素与最后一个元素交换
        swap(0,size-1);
        //2.把最后一个元素删除
        array[--size] = null;
        //3.下潜操作
        down(0);
        return top;
    }

    /**
     * 删除并返回指定索引处的元素
     * @param index 指定索引
     * @return 返回指定索引处的元素
     */
    public Integer poll(int index){
        //0.获取堆顶元素
        Integer deleted = array[index];
        //1.把堆顶元素与最后一个元素交换
        swap(index,size-1);
        //2.把最后一个元素删除
        array[--size] = null;
        //3.下潜操作
        down(index);
        return deleted;
    }

    /**
     * 替换堆顶元素
     * @param replace 新元素
     */
    public void replace(Integer replace){
        array[0] = replace;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     * @param offered 新元素
     * @return 返回是否添加成功，成功->true，失败->false
     */
    public boolean offer(Integer offered){
        if (size == array.length){
            return false;
        }
        up(offered);
        size++;
        return true;
    }

    /**
     * 将offered元素上浮，直至offered元素大于父元素或到达堆顶
     * @param offered
     */
    public void up(Integer offered){
        int child = size;
        array[child] = offered;
        while (child > 0){
            int parent = (child-1)/2;
            if (offered<array[parent]){
                array[child] = array[parent];
            }else {
                break;
            }
            child = parent;
        }
        if (child != size){
            array[child] = offered;
        }
    }
    public boolean isFull(){
        return size == array.length;
    }
    private void down(int i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int min = i;
        if (left < size && array[left] < array[min]){
           min = left;
        }
        if (right < size && array[right] < array[min]){
            min = right;
        }
        if (min != i){
            swap(i,min);
            down(min);
        }
    }
    //交换值
    private void swap(int i,int j){
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[]{4,5,6,1,2,3,7};
        MinHeap minHeap = new MinHeap(array);
        Integer[] ints = minHeap.array;
        System.out.println(Arrays.toString(ints));
        /*MinHeap maxHeap = new MaxHeap(5);
        maxHeap.offer(1);
        maxHeap.offer(4);
        maxHeap.offer(2);
        maxHeap.offer(6);
        maxHeap.offer(3);
        maxHeap.poll();
        maxHeap.poll(2);
        System.out.println(Arrays.toString(maxHeap.array));*/
    }
    /*public static void main(String[] args) {
        Integer[] array = new Integer[]{1,23,5,1,4,62,3};
        MinHeap maxHeap = new MinHeap(array);
        while (maxHeap.size > 1) {
            maxHeap.heapify();
            maxHeap.swap(0,maxHeap.size-1);
            maxHeap.size--;
            maxHeap.down(0);
        }
        System.out.println(Arrays.toString(maxHeap.array));
    }*/
}
